package com.zsj.graph;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/6/2 16:17
 * @description 最小生成树
 * 指的是一个无向图中
 * 能将所有点通过边连起来的最小边权值和
 */
public class MST {
    //思路
    /*
    我们需要定义每个点(from)所对应的to点集合
    一开始所有的点对应的集合只有它们自己
    比如  a <-1-> b <-2-> c
    那我们需要定义a所对应的集合有 {a,b}
    如果a也能到达c 那么需要记录的集合就为 {a,b,c}
    但是我们在合并记录这个集合的时候 我们需要判断是否会产生环
    如果不会有环 就合并集合 否则丢弃
    如何判断是否有环？
        我们只需要判断这个点对应的集合是否和这个点相连的点集合是否相等
        比如a的集合为{a,b,c}
           c的集合为{a,b,c}
          那么c的节点就在a中出现过 就是存在环的情况
           因为我们每次在对节点合并时
           我们需要将这个点对应的集合修改为合并后的集合
           情况示例
           比如一开始
                    a = {a}
                    b = {b}
                    c = {c}
                    d = {d}
           这个时候我们去合并ab节点
           那么她两对应的节点就会为{a,b}
           也就是 a ={a,b}
                 b ={a,b}
            比如我们现在再去合并a和c的节点
            a = {a,b}
            c= {c}
            发现两个集合不是一个 那就合并并且重新指向
            a  = {a,b,c}
            c = {a,b,c}
            再来 我们合并c和d
            c = {a,b,c}
            d = {d}
            一样可以合并并且重新指向
            c = {a,b,c,d}
            d = {a,b,c,d}

            ！！！ 这里我们在去连接a和d
            我们就会发现
            a = {a,b,c,d}
            d = {a,b,c,d}
             可能你会问为什么a变成了abcd 因为a和c指向的集合地址是同一个 你修改了c的集合 也是修改了a的集合
            这里我们就会发现 a 和 d 的集合是同一个内存地址
            那这条边就需要舍弃 因为会导致环

            注意：
            合并集合和判断两个集合是否为同一个的方法
            需要一种数据结构
            叫做 《并查集》

            这叫做K算法
     */

    /*
    思路2  P算法
    任意挑选一个点 从那个点依次扩展得到它的所有边
    用一个小顶堆来记录被解锁的边
    并且挑选一个最小的边 且那个边达到的点没有被到达过
    记录这个到达的点 下次访问时不再次访问这个点
    重复这个过程
    最终就可以得到最小生成树
     */


}
